package EjercicioLista;

import TDALista.BoundaryViolationException;
import TDALista.Dnode;
import TDALista.DoubleLinkedList;
import TDALista.EmptyListException;
import TDALista.InvalidPositionException;
import TDALista.Position;
import TDALista.PositionList;

/**
 * Clase que encapsula dos métodos para resolver el siguiente ejercicio:</br>
 * Escriba dos métodos tales que, considerando dos listas L1 y L2, retorne verdadero si L1 está compuesta por los elementos de L2 en el mismo orden,
 * seguidos de los elementos de L2 en orden inverso. </br>
 * Un método será <i>respeta_formato_sin_acceso</i>, que recibiendo dos listas L1 y L2 resuelve el ejercicio únicamente en términos de las operaciones definidas para el TDA Lista.
 * El otro es un método de la clase lista <i>respeta_formato_sin_acceso</i> que, resuelve el ejercicio recibiendo una lista L2, y considerando a la lista que recibe el mensaje como L1.</br> 
 * 
 * Ejemplo de listas que <b>cumplen</b> con el formato: </br>
 * <ul>
 * <li>L1 = <1,2,3,4,4,3,2,1> </li>
 * <li>L2 = <1, 2, 3, 4> </li>
 * </ul> </br>
 *
 * Ejemplo de listas que <b>no cumplen</b> con el formato: </br>
 * <ul>
 * <li>L1 = L1 = <1,2,3,4,4,3,2,1,5> </li>
 * <li>L2 = <1, 2, 3, 4> </li>
 * </ul> </br>
 * 
 * <b>Requiere:</b> <i>TDALista2</i>.
 * @author FJoaquin (federico.joaquin@cs.uns.edu.ar)
 */
public class EjercicioLista {
	/**
	 * Determina si dadas dos listas L1 y L2, estas cumplen con el formato enunciado.</br>
	 * El método trabaja únicamente haciendo uso de las operaciones definidas por <i>TDALista</i> <b>(sin acceso a la ED)</b>.
	 * @param l1 Lista L1 a considerar para chequear formato enunciado.
	 * @param l2 Lista L2 a considerar para chequear formato enunciado.
	 * @return True si se respeta el formato, false en caso contrario.
	 */
	public static <E> boolean respeta_formato_sin_acceso(PositionList<E> l1, PositionList<E> l2){
		boolean respeta = true;
		Position<E> l1_frente, l1_cola, l2_cursor;
		
		try{
			l1_frente = l1.isEmpty() ? null : l1.first();
			l1_cola = l1.isEmpty() ? null : l1.last();
			l2_cursor = l2.isEmpty() ? null : l2.first();
			
			//Respeta si L1 y L2 están vacías, o si el tamaño de L2 es el doble de L1 cuando ambas no estan vacías. 
			respeta = l1.size() == 2 * l2.size();
			
			//Mientras se respeta el formato y existan elementos en L2 a considerar.
			while(respeta && l2_cursor != null){
				
				//Respeta si los elementos considerados como frente y cola de L1 son iguales al elemento considerado de L2
				respeta = l1_frente.element().equals(l2_cursor.element());
				respeta = respeta && l1_cola.element().equals(l2_cursor.element());
				
				//Se adelanta el cursor de L2 al próximo elemento de la lista, si es que este existe.
				l2_cursor = l2_cursor == l2.last() ? null : l2.next(l2_cursor);
				
				//Se avanza y retrocede el cursor de frente y cola de L1 respectivamente.
				l1_frente = l1.next(l1_frente);
				l1_cola = l1.prev(l1_cola);
			}
		
		}
		catch(EmptyListException e){ respeta = false; }
		catch(InvalidPositionException e1){ respeta = false; }
		catch(BoundaryViolationException e2){ respeta = false; }
		
		return respeta;
	}
	
	/**
	 * Determina si la lista que recibe el mensaje (L1), y una dada lista L2, cumplen con el formato enunciado.</br>
	 * El método <b>posee acceso a la ED</b> de la lista L1 por ser un método de lista, y trabaja únicamente haciendo uso de las operaciones definidas por <i>TDALista</i> <b>(sin acceso a la ED)</b> con la lista L2. </br>
	 * <b>Asume:</b> L1 es una <i>lista doble enlazada sin centinelas</i>.</br>
	 * <b>Requiere:</b> <i>Inicializar</i> las variables <b>frente, cola, y tamaño</b>, que se asumen <i>atributos internos</i> de la clase lista L1.
	 * @param l2 Lista L2 a considerar para chequear formato enunciado.
	 * @return True si se respeta el formato, false en caso contrario.
	 */
	public static <E> boolean respeta_formato_con_acceso(PositionList<E> l2){
		boolean respeta = true;
		Position<E> l2_cursor;
		
		Dnode<E> frente = null;
		Dnode<E> cola = null;
		int tamaño = 1500;
		
		try {
			l2_cursor = l2.isEmpty() ? null : l2.first();
			
			//Respeta si L1 y L2 están vacías, o si el tamaño de L2 es el doble de L1 cuando ambas no estan vacías. 
			respeta = (tamaño == 2 * l2.size());
			
			//Mientras se respeta el formato y existan elementos en L2 a considerar.
			while(respeta && l2_cursor != null){
				
				//Respeta si los elementos considerados como frente y cola de L1 son iguales al elemento considerado de L2
				respeta = frente.element().equals(l2_cursor.element());
				respeta = respeta && cola.element().equals(l2_cursor.element());
				
				//Se adelanta el cursor de L2 al próximo elemento de la lista, si es que este existe.
				l2_cursor = l2_cursor == l2.last() ? null : l2.next(l2_cursor);
				
				//Se avanza y retrocede el cursor de frente y cola de L1 respectivamente.
				frente = frente.getSiguiente();
				cola = cola.getAnterior();
			}
		}
		catch(EmptyListException e1) {respeta = false; }
		catch(InvalidPositionException e2) {respeta = false; }
		catch(BoundaryViolationException e3) { respeta = false; }
		
		return respeta;
	}
	
	
	/**
	 * Genera un string listando los elementos de una PositionList.
	 * Asume que los elementos de tipo E de la lista implementan el método toString().
	 * @param l PositionList de elementos a listar.
	 * @return Listado de los elementos de la PositionList separados por espacios, o "Vacía" si no hay elementos a listar.
	 */
	public static<E> String imprimir(PositionList<E> l){
		String toReturn = "";
		if (l.isEmpty())
			toReturn = "Vacía";
		else
			for(E e : l)
				toReturn += e.toString() + " ";
		return toReturn;
	}
	
	/**
	 * Método que inicia la ejecución del programa. 
	 * Testea el funcionamiento de <i>respeta_formato_sin_acceso</i> con dos listas de prueba.
	 * @param args Argumentos por línea de comandos.
	 */
	public static void main(String [] args){
		PositionList<Integer> l1 = new DoubleLinkedList<Integer>();
		PositionList<Integer> l2 = new DoubleLinkedList<Integer>();
		
		//Testea lista vacía
		System.out.println("L1: " + imprimir(l1));
		System.out.println("L2: " + imprimir(l2));
		System.out.println("Respeta(L1,L2): " + respeta_formato_sin_acceso(l1,l2) + "\n");
		
		//Testea L1 vacía y L2 con elementos.
		l2.addLast(1);
		System.out.println("L1: " + imprimir(l1));
		System.out.println("L2: " + imprimir(l2));
		System.out.println("Respeta(L1,L2): " + respeta_formato_sin_acceso(l1,l2) + "\n");
		
		//Testea L1 con cantidad par de elementos y L2 vacía.
		l1.addLast(1);
		l1.addLast(2);
		l2 = new DoubleLinkedList<Integer>();
		
		System.out.println("L1: " + imprimir(l1));
		System.out.println("L2: " + imprimir(l2));
		System.out.println("Respeta(L1,L2): " + respeta_formato_sin_acceso(l1,l2) + "\n");
		
		//Testea con L1 con cantidad impar de elementos, y L2 vacía.
		l1.addLast(3);
		
		System.out.println("L1: " + imprimir(l1));
		System.out.println("L2: " + imprimir(l2));
		System.out.println("Respeta(L1,L2): " + respeta_formato_sin_acceso(l1,l2) + "\n");
			
		//Testea con L1 = 1 2 3 4 5 5 4 3 2 1 y L2 = 1 2 3 4 5 y 
		l1.addLast(4);
		l1.addLast(5);
		for(int i=1; i<6; i++)
			l2.addLast(i);
		
		for(int i=5; i>0; i--)
			l1.addLast(i);
		
		System.out.println("L1: " + imprimir(l1));
		System.out.println("L2: " + imprimir(l2));
		System.out.println("Respeta(L1,L2): " + respeta_formato_sin_acceso(l1,l2) + "\n");
		
		//Testea con L1 = 1 2 3 4 5 y L2 = 1 2 3 4 5 5 4 3 2 1 
		System.out.println("L1: " + imprimir(l2));
		System.out.println("L2: " + imprimir(l1));
		System.out.println("Respeta(L1,L2): " + respeta_formato_sin_acceso(l2,l1) + "\n");
		
		//Testea con L1 = 1 2 3 4 3 2 1 y L2 = 1 2 3 4
		l1 = new DoubleLinkedList<Integer>();
		for(int i=1; i<5;i++)
			l1.addLast(i);
		
		for(int i=3; i>0; i--)
			l1.addLast(i);
		
		try {
			l2.remove(l2.last());
		} 
		catch (InvalidPositionException e) { } 
		catch (EmptyListException e) { }
		
		System.out.println("L1: " + imprimir(l1));
		System.out.println("L2: " + imprimir(l2));
		System.out.println("Respeta(L1,L2): " + respeta_formato_sin_acceso(l1,l2) + "\n");
	}

}
